package leetcode.d_300_plus;

import java.util.HashMap;
import java.util.Map;

public class P560 {
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        int n = nums.length;
        if (n == 0) {
            return sum;
        }

        int preSum = 0;
        Map<Integer, Integer> map = new HashMap<>(); // 记录前序和的个数
        map.put(0, 1);

        for (int i=0; i<n; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum-k)) {
                sum += map.get(preSum-k);
            }
            int count = map.getOrDefault(preSum, 0);
            map.put(preSum, count+1);
        }
        return sum;
    }
}
